package greddy;

public class _16_738_单调递增的数字 {
    public static int monotoneIncreasingDigits(int n) {

    	String s = String.valueOf(n);
    	char c[] = s.toCharArray();
    	int flag = c.length;
    	// 从后往前遍历，判断前一个值是否比当前值大，是则更新flag
    	// flag用于存储最前面一个需要-1的值，因为后面的所有值都要改成9，这样才是最大值
    	// 不能从前往后，因为如果某个值-1后，后面的值也-1了，导致前面两者又出现冲突，我们就需要回头去处理
    	// 从后往前则只需要不断往前判断处理即可
    	for(int i = c.length - 1; i > 0; i--) {
    		if(c[i-1] > c[i]) {
    			// 前一个值比当前值大，则将前一个值-1
    			// 即使有多个i-1被修改，在最后一次flag后面修改过的都会被改成9
    			c[i-1]--;
    			flag = i;
    		}
    	}
    	
    	// flag后的值都改成9
    	// flag初始值是c.length，只有上面出现x>y的情况才会修改flag，才会触发这里的修改flag后面的9
    	for(int i = flag; i < c.length; i++) {
    		c[i] = '9';
    	}
    	
    	
    	return Integer.parseInt(String.valueOf(c));
    }
    
    public static boolean check(int n) {
    	String s = String.valueOf(n);
    	for(int i = 0; i < s.length() - 1; i++) {
    		// 一旦比后面一个值大，说明当前的值不符合
    		if(s.charAt(i) > s.charAt(i+1)) {
    			return false;
    		}
    	}
    	return true;
    }
    
    public static void main(String[] args) {
//		System.out.println(monotoneIncreasingDigits(777616726));
		System.out.println(monotoneIncreasingDigits(332));

	}
}
